package com.bm;

import java.util.HashSet;
import java.util.Set;

/**
 * Description: BM65 最长公共子序列(二)
 *
 * @author weiruibai.vendor
 * Date: 2022/11/4 14:03
 */
public class BM65 {

    public static void main(String[] args) {

        BM65 bm65 = new BM65();
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23A456A";

        /**
         * EKhHnp06qE75TmA7036PyZdlzad49gGNsEAe0830ozh5zKD1w3ngrA7VA0OvK15v12WzqDERP375C3NJKP934O8Ix0NF412B6Kk2hbALBzYFq66r0BuSPt1KD816nwOWB0M1dK2Cg1s9O6IfQTS0bT852U78SSjk4astw2KKvudmsavy2699Ut1DN3bp0cbJuB131j6W8L7NTf8NnfznSWtF7g3UDB9O68UXU730f02WLnPGCcHOn0SRnnuXrQ862Z77Jo24H3WAmEZG5BbKztIec1OFr7kXS54k1HBN5Mqx5f6SzL6Po3LDXmIlb613ZBozxg5c9Uc3Bnssp17E1ch2ZS5LGn4TYf2CN88J2GC43k12hV4zeg23S4D3LNM31R6R3JuoMDBwHc349pzjmb7nCxWysf9csh4vC30k5185H023UI6E2Eiwys8bhb97CoDv16X40iNgb89O0c2C4y0Ew0FoHSFyePi34s2ik9H5KFgD7aCbar29j2bNxGo7ym1xO5VQouJAhmAZhBVHF6QPspcvn90zH8B2928Lae8a6JD28z38Z56Urr1MB8753xi5NfdGqA5CekTU0MStGmDBOzTE0GAfc3ygNLLTe0rwQ2WN4rX62YiwOBkX3OUJt8IR2Z7xv6u3g0E3498072lOGX6nm6zQJsV38HN4IFL9ekbWdMEr904wkK4mbEjz0ff3NB7G1x4Q42o9X2Vj5kDuSFl7HOT8CyMzw18kVoiDj3ri0EB2zl585M93rdOlcXL1acrR4m1VmRNRkj6YOsxa7g841UG77T5e2N61iZ1375A9BMKj5Li15rNKR33dXU6dNASuEBTgL4IR347M6kK40L6ui7uLW64qIUpPZvy5s3LP9827FWJEH98aB68rhp8xqUhJ6VPv4HJudP1l5wwL7g2B2o9s9P377Ed4c24e5HmDs5RU8YbB9uCGHC5da081o4C26FhJR8NSe0tIKoHPgbq31zNEmDo1nF3l1O4aSy0LF9dfthJFy0nWzyMdCy6du3bRNF8z93MKF1bJbehe16cqHXqFJI54aE3K9h8pooBgSqG4U9FH2eZT3IB21RJH24e9lrGpE8l22WOB3WmMj806890C45Few54gN5F1jBO2Ge5KqSopHaqK2FkvVStbeFkz4p143709gLtwIiww9E2Eg9VPty7Jx7ej7nmW5rfpnfwXWiD6zNg9z7J2ybs96l23868bytw8cA0H2kAA1QOidYvrA255bAZt0x5GTIrOP5I0ynCRsT54MYiDgFkJX7I7X9F2K3n369GOl8Ih3w7vwpq4f214e2l0745K9ighL6Pz7PNCO8oP5YNQ3oHXK7HV82bUSPk19kwu8xRRp8mNBAeo2W7yMe64UQD6W95fFo1NS2Q49e958w493WVL3O2t98Au6P3z3Bifb2bmQL1GXcL9VT1X3EgnmvnN03yqGVt278KLL5rJv05U7GUFOi957m8UFn5156Bg9ZcC9OM4Y2jdI1590XO9SrOF222gG13fP9WCNZ47298lZKA5h4sA20pyDqao3PP5YCCcIfTvsYy2ZR5w93s4Y8j0as32gy0ItXOzpqyp7hzik9P958hh8rEULpx1q63bo51Y3s8jLpCusP7O34REDjmixA2s2i4wbcVVshrvio1E4dJB77r2X6J3j8oW6LfmDuDpy3xy5wnJzAwjS5T78
         * kQlReRfFX
         */
      /*  s1 = "bsbininm";
        s2 = "jmjkbkjkv";
        s1 = "pmjghexybyrgzczy";
        s2 = "hafcdqbgncrcbihkd";*/
        /*s1 = "111";
        s2 = "222";*/
        /*s1 = "EKhHnp06qE75TmA7036PyZdlzad49gGNsEAe0830ozh5zKD1w3ngrA7VA0OvK15v12WzqDERP375C3NJKP934O8Ix0NF412B6Kk2hbALBzYFq66r0BuSPt1KD816nwOWB0M1dK2Cg1s9O6IfQTS0bT852U78SSjk4astw2KKvudmsavy2699Ut1DN3bp0cbJuB131j6W8L7NTf8NnfznSWtF7g3UDB9O68UXU730f02WLnPGCcHOn0SRnnuXrQ862Z77Jo24H3WAmEZG5BbKztIec1OFr7kXS54k1HBN5Mqx5f6SzL6Po3LDXmIlb613ZBozxg5c9Uc3Bnssp17E1ch2ZS5LGn4TYf2CN88J2GC43k12hV4zeg23S4D3LNM31R6R3JuoMDBwHc349pzjmb7nCxWysf9csh4vC30k5185H023UI6E2Eiwys8bhb97CoDv16X40iNgb89O0c2C4y0Ew0FoHSFyePi34s2ik9H5KFgD7aCbar29j2bNxGo7ym1xO5VQouJAhmAZhBVHF6QPspcvn90zH8B2928Lae8a6JD28z38Z56Urr1MB8753xi5NfdGqA5CekTU0MStGmDBOzTE0GAfc3ygNLLTe0rwQ2WN4rX62YiwOBkX3OUJt8IR2Z7xv6u3g0E3498072lOGX6nm6zQJsV38HN4IFL9ekbWdMEr904wkK4mbEjz0ff3NB7G1x4Q42o9X2Vj5kDuSFl7HOT8CyMzw18kVoiDj3ri0EB2zl585M93rdOlcXL1acrR4m1VmRNRkj6YOsxa7g841UG77T5e2N61iZ1375A9BMKj5Li15rNKR33dXU6dNASuEBTgL4IR347M6kK40L6ui7uLW64qIUpPZvy5s3LP9827FWJEH98aB68rhp8xqUhJ6VPv4HJudP1l5wwL7g2B2o9s9P377Ed4c24e5HmDs5RU8YbB9uCGHC5da081o4C26FhJR8NSe0tIKoHPgbq31zNEmDo1nF3l1O4aSy0LF9dfthJFy0nWzyMdCy6du3bRNF8z93MKF1bJbehe16cqHXqFJI54aE3K9h8pooBgSqG4U9FH2eZT3IB21RJH24e9lrGpE8l22WOB3WmMj806890C45Few54gN5F1jBO2Ge5KqSopHaqK2FkvVStbeFkz4p143709gLtwIiww9E2Eg9VPty7Jx7ej7nmW5rfpnfwXWiD6zNg9z7J2ybs96l23868bytw8cA0H2kAA1QOidYvrA255bAZt0x5GTIrOP5I0ynCRsT54MYiDgFkJX7I7X9F2K3n369GOl8Ih3w7vwpq4f214e2l0745K9ighL6Pz7PNCO8oP5YNQ3oHXK7HV82bUSPk19kwu8xRRp8mNBAeo2W7yMe64UQD6W95fFo1NS2Q49e958w493WVL3O2t98Au6P3z3Bifb2bmQL1GXcL9VT1X3EgnmvnN03yqGVt278KLL5rJv05U7GUFOi957m8UFn5156Bg9ZcC9OM4Y2jdI1590XO9SrOF222gG13fP9WCNZ47298lZKA5h4sA20pyDqao3PP5YCCcIfTvsYy2ZR5w93s4Y8j0as32gy0ItXOzpqyp7hzik9P958hh8rEULpx1q63bo51Y3s8jLpCusP7O34REDjmixA2s2i4wbcVVshrvio1E4dJB77r2X6J3j8oW6LfmDuDpy3xy5wnJzAwjS5T78";
        s2 = "kQlReRfFX";*/
        System.out.println(bm65.LCS_dp(s1, s2));
    }

    public String LCS_dp(String s1, String s2) {
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
            return "-1";
        }
        // 压缩
        String[] strs = compressStr(s1, s2);
        s1 = strs[0];
        s2 = strs[1];
        if (s1.length() == 0 || s2.length() == 0) {
            return "-1";
        }
        int N = s1.length();
        int M = s2.length();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int[][] dp = new int[N][M];
        dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
        for (int i = 1; i < M; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], chars1[0] == chars2[i] ? 1 : 0);
        }
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], chars1[i] == chars2[0] ? 1 : 0);
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                int val = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (chars1[i] == chars2[j]) {
                    val = Math.max(val, dp[i - 1][j - 1] + 1);
                }
                dp[i][j] = val;
            }
        }
        /**
         * s1 = "1A2C3D4B56";
         * s2 = "B1D23A456A";
         * 对应dp为
         * dp=
         *    0  1  2  2  3  4  5  6  7  8
         * 0 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
         * 1 [0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
         * 2 [0, 1, 1, 2, 2, 2, 2, 2, 2, 2]
         * 3 [0, 1, 1, 2, 2, 2, 2, 2, 2, 2]
         * 4 [0, 1, 1, 2, 3, 3, 3, 3, 3, 3]
         * 5 [0, 1, 2, 2, 3, 3, 3, 3, 3, 3]
         * 6 [0, 1, 2, 2, 3, 3, 4, 4, 4, 4]
         * 7 [1, 1, 2, 2, 3, 3, 4, 4, 4, 4]
         * 8 [1, 1, 2, 2, 3, 3, 4, 5, 5, 5]
         * 9 [1, 1, 2, 2, 3, 3, 4, 5, 6, 6]
         * 从dp右下角开始
         * 步骤1、先横向从右往左找到第一个不想等的项
         * 步骤2、在步骤1上，纵向从上到上找到不想等的想，那么该坐标对应的字符串下标就是答案其中的一个值
         * 总之：从右下角开始，找到当前数字最左且最上的位置，然后找到该字符串所在位置
         * 例如：
         * 上面的dp
         * 答案：从右下角开始(9,7)(8,6)(6,5)(4,3)(2,2)(1,1)倒过来就是答案
         *
         */
        N--;
        M--;
        int length = dp[N][M];
        if (length == 0) {
            return "-1";
        }
        char[] res = new char[length];
        length--;

        while (length >= 0) {
            if (M > 0 && dp[N][M] == dp[N][M - 1]) {
                M--;
            } else if (N > 0 && dp[N][M] == dp[N - 1][M]) {
                N--;
            } else {
                res[length--] = chars1[N];
                N--;
                M--;
            }
        }
        return String.valueOf(res);
    }

    /**
     * 压缩，只处理有公共字符的
     *
     * @param s1
     * @param s2
     * @return
     */
    private String[] compressStr(String s1, String s2) {
        int N = s1.length();
        int M = s2.length();
        Set<Character> repeat = new HashSet<>();
        String shortStr = s1;
        String longStr = s2;
        if (N > M) {
            shortStr = s2;
            longStr = s1;
        }
        for (char ch : shortStr.toCharArray()) {
            repeat.add(ch);
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : longStr.toCharArray()) {
            if (repeat.contains(ch)) {
                sb.append(ch);
            }
        }
        return new String[]{shortStr, sb.toString()};
    }


}
